package j2024.j202411;

import java.util.ArrayList;
import java.util.List;

public class j1115 {
    /**
     * 22. 括号生成
     * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
     */
    int left,right,nn;
    List<String> ret;
    StringBuilder path;
    public List<String> generateParenthesis(int n) {
        nn = n;
        left = 0;right = 0;
        ret = new ArrayList<>();
        path = new StringBuilder();
        dfs();
        return ret;
    }
    public void dfs(){
        if(right==nn){
            ret.add(path.toString());
            return;
        }
        if(left<nn){
            path.append("(");
            left++;
            dfs();
            path.deleteCharAt(path.length()-1);
            left--;
        }
        if(right<left){
            path.append(")");
            right++;
            dfs();
            path.deleteCharAt(path.length()-1);
            right--;
        }
    }

    /**
     * 79. 单词搜索
     * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。
     * 如果 word 存在于网格中，返回 true ；否则，返回 false 。
     *
     * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，
     * 其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
     */
    char[] words;
    boolean[][] vis;
    int[] dx = {0,0,-1,1};
    int[] dy = {1,-1,0,0};
    int m,n;
    public boolean exist(char[][] board, String word) {
        words = word.toCharArray();
        m = board.length;n = board[0].length;
        vis = new boolean[board.length][board[0].length];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(board[i][j] == words[0]) {
                    vis[i][j] = true;
                    if(isOrNot(board,i,j,1)){
                        return true;
                    }
                    vis[i][j] = false;
                }
            }
        }
        return false;
    }
    public boolean isOrNot(char[][] borad,int i,int j,int wi){
        if(wi == words.length){
            return true;
        }
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k],y = j + dy[k];
            if(x>=0 && x<m && y>=0 && y<n && borad[x][y] == words[wi] && !vis[x][y]){
                vis[x][y] = true;
                if(isOrNot(borad,x,y,wi+1)){
                    return true;
                }
                vis[x][y] = false;
            }
        }
        return false;
    }
}
